package 数组.移除元素_快慢指针;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/1/11 14:35
 * @description:给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度
 * @version:
 */

//快慢指针的思想
public class Solution {
    public static void main(String[] args) {
        int[] arr = {1,2,3,3,4,5};
        int target = 3;
        remove2(arr,target);
    }

    //快慢指针  牛逼！！！！
    public static int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }

    //快慢指针
    public static int remove2(int[] nums,int val) {
        int fast = 0;
        int slow = 0;
        while (fast <= nums.length - 1) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    //双向指针法
    public static int removeElement2(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(right >= 0 && nums[right] == val) right--; //将right移到从右数第一个值不为val的位置
        while(left <= right) {
            if(nums[left] == val) { //left位置的元素需要移除
                //将right位置的元素移到left（覆盖），right位置移除
                nums[left] = nums[right];
                right--;
            }
            left++;
            while(right >= 0 && nums[right] == val) right--;
        }
        return left;
    }
}
